package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 14:57
 */
class P53II {

    private fun missingNumber(nums: IntArray): Int {
        if (nums.size == 1) {
            return if (nums[0] == 1) 0 else 1
        }

        var left = 0
        var right = nums.size - 1
        var mid: Int
        while (left < right) {
            if (right - left <= 3)
                return check(nums, left, right)
            mid = (left + right).shr(1)
            val midValue = nums[mid]
            if (midValue <= mid) {
                left = mid
            } else {
                right = mid
            }
        }
        return nums.size // no found
    }

    private fun check(nums: IntArray, left: Int, right: Int): Int {
        for (idx in left..right)
            if (nums[idx] != idx)
                return idx
        return right + 1 // no found
    }

    @Test
    fun test0() {
        Tester.createTest(this::missingNumber)
            .addCase(intArrayOf(0, 1, 3), 2)
            .addCase(intArrayOf(0, 1, 2, 3, 4, 5, 6, 7, 9), 8)
            .addCase(intArrayOf(1, 2, 3), 0)
            .addCase(intArrayOf(0), 1)
            .addCase(intArrayOf(1), 0)
            .addCase(intArrayOf(1, 2), 0)
            .addCase(intArrayOf(0, 1), 2)
            .testAndShow()
    }

}
